#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/24
# @Author   :Changshu
# @File     :Exercise_637_BFS.py
# 637. 二叉树的层平均值
# 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

# Definition for a binary tree node.
class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

class Solution:
	'''深度优先,使用两个列表存储每层结点值的和和每层的结点数---代码写的不够简洁
	counts=[]
	sums=[]
	averages=[]
	def averageOfLevels(self, root: TreeNode) -> list:
		def dfs(root:TreeNode,level:int,counts:list,sums:list):
			if not root:
				return
			if level<len(sums):
				sums[level] +=root.val
				counts[level]+=1
			else:
				sums.append(root.val)
				counts.append(1)
			dfs(root.left,level+1,counts,sums)
			dfs(root.right, level + 1, counts, sums)
		dfs(root,0,self.counts,self.sums)
		for i in range(len(self.counts)):
			s=self.sums[i]
			c=self.counts[i]
			self.averages.append(s/c)
		return self.averages


	def averageOfLevels(self, root: TreeNode) -> list:
		def dfs(root:TreeNode,level:int):
			if not root:
				return
			if level<len(sums):
				sums[level]+=root.val
				counts[level]+=1
			else:
				sums.append(root.val)
				counts.append(1)
			dfs(root.left,level+1)
			dfs(root.right, level + 1)
		sums=[]
		counts=[]
		dfs(root,0)
		return [s/c for s,c in zip(sums,counts)]
	'''

	'''法二：广度优先。层序遍历'''
	def averageOfLevels(self, root: TreeNode) -> list:
		averages=[]
		if not root:
			return averages
		queue=[root]
		while queue:
			total=0
			size=len(queue)
			for i in range(size):
				node=queue.pop(0)
				total+=node.val
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
			averages.append(total/size)
		return averages


if __name__ == '__main__':
	root=TreeNode(3)
	node2_1=TreeNode(9)
	node2_2 = TreeNode(20)
	node3_1=TreeNode(15)
	node3_2 = TreeNode(7)

	root.left=node2_1
	root.right=node2_2
	node2_2.left=node3_1
	node2_2.right=node3_2

	solution=Solution()
	print(solution.averageOfLevels(root))

